By using SIAM Journals Online you agree to abide by the
Terms and Conditions of Use.

©  SIAM

 

SIAM Journal on Computing

Table of Contents
Search This Issue
Volume 21, Issue 3, pp. 407-599

Please Note: Electronic articles are available well in advance of the printed articles.

What Article options are available ?   View Cart   

On the Exact Complexity of String Matching: Upper Bounds

Zvi Galil and Raffaele Giancarlo

pp. 407-437

BibTeX  Abstract Full Text:  PDF

Probably Approximate Learning over Classes of Distributions

B. K. Natarajan

pp. 438-449

BibTeX  Abstract Full Text:  PDF

The Complexity of the Lin–Kernighan Heuristic for the Traveling Salesman Problem

Christos H. Papadimitriou

pp. 450-465

BibTeX  Abstract Full Text:  PDF

Optimal Parallel Randomized Algorithms for Three-Dimensional Convex Hulls and Related Problems

John H. Reif and Sandeep Sen

pp. 466-485

BibTeX  Abstract Full Text:  PDF

Processor Efficient Parallel Algorithms for the Two Disjoint Paths Problem and for Finding a Kuratowski Homeomorph

Samir Khuller, Stephen G. Mitchell, and Vijay V. Vazirani

pp. 486-506

BibTeX  Abstract Full Text:  PDF

Algorithms for Splicing Systems

R. W. Gatterdam

pp. 507-520

BibTeX  Abstract Full Text:  PDF

Relating Equivalence and Reducibility to Sparse Sets

Eric Allender, Lane A. Hemachandra, Mitsunori Ogiwara, and Osamu Watanabe

pp. 521-539

BibTeX  Abstract Full Text:  PDF

Ray Shooting and Other Applications of Spanning Trees with Low Stabbing Number

Pankaj K. Agarwal

pp. 540-570

BibTeX  Abstract Full Text:  PDF

The Nilpotency Problem of One-Dimensional Cellular Automata

Jarkko Kari

pp. 571-586

BibTeX  Abstract Full Text:  PDF

Learning Monotone Boolean Functions by Uniformly Distributed Examples

Qian Ping Gu and Akira Maruoka

pp. 587-599

BibTeX  Abstract Full Text:  PDF